package leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
 * <p>
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abc"
 * 输出: 3
 * 解释: 三个回文子串: "a", "b", "c".
 * 示例 2:
 * <p>
 * 输入: "aaa"
 * 输出: 6
 * 说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
 * 注意:
 * <p>
 * 输入的字符串长度不会超过1000。
 * <p>
 * <p>
 * 判断是否是回文子串见{@link Code05_LongestPalindrome}
 * 判断是否是回文子串见{@link Code05_LongestPalindrome2}
 *
 * @date 2020/5/26 16:09
 */
public class Code647_回文子串个数 {

    /**
     * 方式1：暴力遍历所有子串，判断每个子串是否是回文串。
     * O(n^3)  682ms
     */
    public static int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    private static boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j--;
            } else {
                return false;
            }
        }
        return true;
    }

    /**
     * 方式2：往外扩，扩的过程中去判断是否是回文子串，并记录全局结果
     * 11ms 时间O(n^2)
     */
    public static int countSubstrings1(String s) {
        if (s == null || s.length() == 0) return 0;
        int res = 0;
        s = getModify(s);
        for (int i = 0; i < s.length(); i++) {
            //奇回文即可。 1被修饰为#1#，
            // 11被修饰为#1#1#。都是奇回文。
            res += expand(s, i, i);
            res += expand(s, i, i + 1);
        }
        return res;

    }


    /**
     * 方式3：对字符串处理，统一处理为奇数个。
     * TODO BUG #1#本来是1个，但是处理的时候是3个
     * TODO BUG 1#1本来是2个，但是处理的时候是3个
     *
     * @param s
     * @return
     */
    public static int countSubstrings2(String s) {
        if (s == null || s.length() == 0) return 0;
        int res = 0;
        s = getModify(s);
        for (int i = 0; i < s.length(); i++) {
            //如果i是偶数，那么以#为中心，# -> 0,  1#1 -> 2, #1#1# ->2
            // 11被修饰为#1#1#。都是奇回文。
            int count = expand(s, i, i);

        }
        return res;
    }

    private static String getModify(String s) {
        StringBuffer sb = new StringBuffer("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString();
    }

    private static int expand(String s, int i, int j) {
        int count = 0;
        //当前是回文
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
            count++;
        }
        return count;
    }
}
